package leetcode.matrix;

import java.util.Arrays;

/**
 * 给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
 * 输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
 *  
 *
 * 提示：
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 100
 * 1 <= mat[i][j] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-the-matrix-diagonally
 */
public class 将矩阵按对角线排序 {

    public static int[][] diagonalSort(int[][] mat) {
        int m = mat.length; // x \
        int n = mat[0].length; // y -
        for (int i = 0; i < n+m-1; i++){
            int x;
            int y;
            if (i < m -1 ){
                x = m - 1 - i;
                y = 0;
            }else {
                x = 0;
                y = i - m + 1;
            }
            int length = Math.min(m - x, n - y);
            int [] tmp = new int[length];
            for (int j = 0; j < length; j ++){
                tmp[j] = mat[x+j][y+j];
            }
            Arrays.sort(tmp);
            for (int j = 0; j < length; j ++){
                 mat[x+j][y+j] = tmp[j];
            }
        }
        return mat;
    }

    public static void main(String[] args){
        int[][] a = new int[][]{{1,2},{1,3},{4,2},{5,1},{2,6},{7,5},{8,7},{9,7}};

        for (int[] i : a){
            for (int j : i){
                System.out.printf("%d,", j);
            }
            System.out.print("\n");
        }
        diagonalSort(a);
        for (int[] i : a){
            for (int j : i){
                System.out.printf("%d,", j);
            }
            System.out.print("\n");
        }
    }
}
